package main

import "fmt"

func main() {
	a := "ababaeabacaaaaaddfdfdfdfdf"
	b := "aacbdaac"
	pos := Kmp(b, a)
	fmt.Println(pos)
}
func Kmp(needle string, str string) int {
	next := getNext(needle)
	fmt.Println(next)
	j := 0
	for i := 0; i < len(str); i++ {
		for j > 0 && str[i] != needle[j] {
			j = next[j-1] + 1
		}
		if str[i] == needle[j] {
			j++
		}
		if j == len(needle) {
			return i - j + 1
		}
	}
	return -1
}
// 辅助函数
// 找最大长度的相同前缀和后缀
// 这样在匹配字符串失败的时候，
// 由于前缀和后缀是相同的，比如： aacbdaac
// aac 最大为3 相同的前缀aac，后缀aac，
// 所以可以直接跳到后缀的起点，略过了aacbd
func getNext(needle string) []int {
	// aaddf
	var next = make([]int, len(needle))
	fmt.Println(next)
	next[0] = -1
	k := -1
	for i := 1; i < len(needle); i++ {
		for k != -1 && needle[k+1] != needle[i] {
			k = next[k]
		}
		if needle[k+1] == needle[i] {
			k++
		}
		next[i] = k
	}
	return next
}